package com.clstu.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * 用LinkedList双端队列实现滑动窗口
 * 题目:leetCode 239
 *
 * 给你一个整数数组 nums，有一个大小为的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。

 *
 */
public class DeQueue {

    public static void main(String[] args) {

//        new HashMap<>().en

        char[] s = {'a'};
        String regStr = new String(s);
        System.out.println(s);

        //测试滑动窗口实现双端队列
        int[] nums = {1,3,-1,-3,5,3,6,7};
        DeQueue deQueue = new DeQueue(nums);
        int k = 3;
        for (int i = 0;i<k;i++){
            deQueue.moveRight();
        }
        int[] res = new int[nums.length - k + 1];
        for (int i = 0;i<res.length;i++){
            res[i] = deQueue.moveLeft();
            deQueue.moveRight();
        }
        System.out.println(Arrays.toString(res));
    }

    //队列里面存的是数组的下标,
    // R表示的是窗口最右值,每次加入的数值的下标就是R
    public LinkedList<Integer> deQueue;
    public int[] nums;
    public int L;
    public int R;
    //构造器
    public DeQueue(int[] nums){
        this.nums = nums;
        deQueue = new LinkedList<>();
        L = -1;
        R = 0;
    }

    //窗口右侧右移
    public void moveRight(){
        //如果已经越界,返回
        if(R >= nums.length) return;
        //跟最顶元素比较
        while(true){
            //如果可以入队列
            if(deQueue.isEmpty() ||  nums[R] < nums[deQueue.getLast()]){
                deQueue.add(R++);
                break;
            }else{
                deQueue.removeLast();
            }
        }
        System.out.println(" ----R>"+"  L="+L+" R="+R+"   "+deQueue);
    }

    //窗口左侧右移,并返回当前窗口范围内的最大值
    public int moveLeft(){
        L++;
        //如果该队列首保存的下标刚好过期,删除,否则直接返回最大值即可
        int res = 0;
        if(L == deQueue.getFirst()){
            res =  nums[deQueue.removeFirst()];
        }else {
            res = nums[deQueue.getFirst()];
        }
        System.out.println(" L---->"+"  L="+L+" R="+R+"   "+deQueue);
        return res;
    }

}
